package com.vilynn.interview.nowcoder;

public class NC88 {

    public static void main(String[] args) {
        int[] a = new int[]{1332802, 1177178, 1514891, 871248, 753214, 123866, 1615405, 328656, 1540395, 968891, 1884022, 252932, 1034406, 1455178, 821713, 486232, 860175, 1896237, 852300, 566715, 1285209, 1845742, 883142, 259266, 520911, 1844960, 218188, 1528217, 332380, 261485, 1111670, 16920, 1249664, 1199799, 1959818, 1546744, 1904944, 51047, 1176397, 190970, 48715, 349690, 673887, 1648782, 1010556, 1165786, 937247, 986578, 798663};
        System.out.println(findKth(a, a.length, 24));
    }


    public static int findKth(int[] a, int n, int K) {
        // write code here
        int baseIndex = sort(a, n, K, 0);
        return a[baseIndex];
    }

    public static int sort(int[] a, int n, int K, int baseIndex) {
        int base = a[baseIndex];
        for (int i = baseIndex + 1; i < n; i++) {
            if (a[i] >= base) {
                int temp = a[i];
                a[i] = a[baseIndex + 1];
                a[baseIndex + 1] = a[baseIndex];
                a[baseIndex] = temp;
                baseIndex++;
            }
        }
        if (baseIndex == K - 1) {
            return baseIndex;
        } else if (baseIndex > K - 1) {
            return sort(a, baseIndex, K, 0);
        } else if (baseIndex < K - 1) {
            return sort(a, n, K, baseIndex + 1);
        }
        return baseIndex;
    }

}
